//
// Created by mazaiting on 2021/12/19.
//

#include <stdio.h>
#include <time.h>

#include "search_menu.h"
#include "seq_search.h"
#include "bst_search.h"
#include "avl_search.h"
#include "hash_search.h"
#include "btree.h"
#include "bp_tree.h"
#include "rb_search.h"

// 顺序表
int seq_arr[] = {1, 2, 3, 4, 5, 6};

// 二分查找
int bin_arr[] = {5, 13, 19, 21, 37, 56, 64, 75, 80, 88, 92};

/**
 * 顺序查找表
 */
void seq_search_run();

/**
 * 二分查找
 */
void bin_search_run();

/**
 * 二叉搜索
 */
void bst_search_run();

/**
 * 平衡二叉树
 */
void avl_run();

/**
 * 哈希表构建
 */
void hash_run();

/**
 * B 树
 */
void b_tree_run();

/**
 * B+树
 */
void bp_tree_run();

/**
 * 红黑树
 */
void rb_tree_run();

void search_run() {
    // 菜单
    int menu = -1;
    // 是否运行
    Status is_run = TRUE;
    while (is_run) {
        printf("╔═══════════════════════════════════════════════╗\n");
        printf("║                     查找算法                  ║\n");
        printf("║ 1: 顺序查找                                   ║\n");
        printf("║ 2: 二分查找                                   ║\n");
        printf("║ 3: 二叉搜索                                   ║\n");
        printf("║ 4: 平衡二叉树                                 ║\n");
        printf("║ 5: 哈希表                                     ║\n");
        printf("║ 6: B树                                        ║\n");
        printf("║ 7: B+树                                       ║\n");
        printf("║ 8: 红黑树                                     ║\n");
        printf("║ 0: 退出                                       ║\n");
        printf("╚═══════════════════════════════════════════════╝\n");
        printf("请选择功能菜单: ");
        fflush(stdout);
        scanf("%d", &menu);

        switch (menu) {
            case 0:
                // 退出
                is_run = FALSE;
                break;
            case 1:
                seq_search_run();
                break;
            case 2:
                bin_search_run();
                break;
            case 3:
                bst_search_run();
                break;
            case 4:
                avl_run();
                break;
            case 5:
                hash_run();
                break;
            case 6:
                b_tree_run();
                break;
            case 7:
                bp_tree_run();
                break;
            case 8:
                rb_tree_run();
                break;
            default:
                printf("输入异常\n");
                break;
        }
    }
}

void seq_search_run() {
    SSTable *st;
    Create_SSTable(&st, 6, seq_arr);
    printf("创建顺序表完成\n");
    SSTable_Print(st);
    printf("请输入查找数据的关键字: \n");
    fflush(stdout);
    int key;
    scanf("%d", &key);
    int location = Search_Seq(st, key);
    if (location == 0) {
        printf("查找失败");
    } else {
        printf("数据在查找表中的位置为：%d", location);
    }
}

void bin_search_run() {
    SSTable *st;
    Create_SSTable(&st, 11, bin_arr);
    printf("创建二分查找顺序表完成\n");
    SSTable_Print(st);
    printf("请输入查找数据的关键字：\n");
    fflush(stdout);
    int key;
    scanf("%d", &key);
    int location = Search_Bin(st, key);
    //如果返回值为 0，则证明查找表中未查到 key 值，
    if (location == 0) {
        printf("查找表中无该元素");
    } else {
        printf("数据在查找表中的位置为：%d", location);
    }
}

/**
 * 二叉搜索
 */
void bst_search_run() {
    // 二叉树数据
//    int a[5] = {3, 4, 2, 5, 9};
    int a[] = {45, 24, 53, 12, 37, 93};
    BstTree t = NULL;
    // 循环插入数据
    for (int i = 0; i < (sizeof(a) / sizeof(int)); ++i) {
        BST_Insert(&t, a[i]);
    }
    printf("中序遍历二叉排序树：\n");
    InOrderBstTraverse(t);
    printf("\n");
    printf("删除3后，中序遍历二叉排序树：\n");
    BST_Delete(&t, 45);
    printf("中序遍历二叉排序树：\n");
    InOrderBstTraverse(t);
    printf("\n");
}

void avl_run() {
    // 测试数据
    int arr[] = {1, 23, 45, 34, 98, 9, 4, 35, 23};
    bool taller;
    AvlTree t = NULL, pos;
    // 构建平衡二叉树
    for (int i = 0; i < (sizeof(arr) / sizeof(int)); ++i) {
        AVL_Insert(&t, arr[i], &taller);
    }
    //中序遍历输出
    InOrderAvlTraverse(t);
    printf("\n");
    //判断平衡二叉树中是否含有数据域为 4 的数据
    if (Find_Node(t, 4, &pos))
        printf("数据所在的位置: %d\n", pos->data);
    else
        printf("Not find this Node\n");
}

void hash_run() {
    HashTable ht;
    // 初始化
    Hash_Table_Init(&ht);
    // 插入数据
    Hash_Table_Insert(&ht, 1, 1);
    Hash_Table_Insert(&ht, 2, 2);
    Hash_Table_Insert(&ht, 101, 101);
    Hash_Table_Insert(&ht, 102, 102);
    Hash_Table_Insert(&ht, 1001, 1001);
    Hash_Table_Print(&ht);
    HashValueType value = 0;
    int key = 102;
    int ret = Hash_Table_Find(&ht, key, &value);
    printf("查询到的位置: %d, 键: %d, 值: %d\n", ret, key, value);
    // 移除元素
    Hash_Table_Remove(&ht, key);
    Hash_Table_Print(&ht);
}

void b_tree_run() {
    BTNode *t = NULL;
    // 查找结果
    BResult s;
    // 数据
    BKeyType a[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15};
    printf("创建一棵%d阶B树:\n", bOrder);
    for (int i = 0; i < 15; ++i) {
        // 在树中查找关键字
        s = Search_BTree(t, a[i]);
        // 如果没有查找到就插入
        if (!s.tag) {
            Insert_BTree(&t, s.i, a[i], s.pt);
        }
        printf("   第%d步,插入元素%d:\n ", i + 1, a[i]);
        Print_BTree(t);
    }
    printf("\n");
    printf("删除操作: \n");
    int k = 9;
    Delete_BTree(t, k);
    printf("  删除%d:\n ", k);
    printf("  删除后的B树: \n");
    Print_BTree(t);
    printf("\n");

    k = 1;
    Delete_BTree(t, k);
    printf("  删除%d:\n ", k);
    printf("  删除后的B树: \n");
    Print_BTree(t);
    printf("\n");

    printf("  递归释放B树\n");                       //递归释放B树
    Destroy_BTree(&t);
    Print_BTree(t);
}

/**
 * B+树
 */
void bp_tree_run() {
    BPTree t;
    t = BP_Initialize();
    clock_t c1 = clock();
    // 插入 20 个元素
    int sum = 20;
    printf("================插入数据================\n");
    while (sum > 0) {
        t = BP_Insert(t, sum--);
        BP_Travel(t);
        // 将输出的内容从缓冲区刷新出来
        fflush(stdout);
    }

    printf("================移除数据================\n");
    sum = 1;
    while (sum < 5) {
        t = BP_Remove(t, sum++);
        BP_Travel(t);
        // 将输出的内容从缓冲区刷新出来
        fflush(stdout);
    }

    printf("================打印数据================\n");
    BP_Travel_Data(t);

    printf("================销毁B+树================\n");
    BP_Destroy(t);
    clock_t c2 = clock();
    printf("\n用时： %lu秒\n", (c2 - c1) / CLOCKS_PER_SEC);
}

void rb_tree_run() {
    int a[] = {10, 40, 30, 60, 90, 70, 20, 50, 80};
    // 计算数组长度
    int len = sizeof(a) / sizeof(a[0]);
    RBRoot *root = NULL;
    // 创建红黑树根
    root = RB_Create_Tree();
    printf("== 原始数据: ");
    for (int i = 0; i < len; i++)
        printf("%d ", a[i]);
    printf("\n");

    for (int i = 0; i < len; i++) {
        RB_Insert_Tree(root, a[i]);
        printf("== 添加节点: %d\n", a[i]);
        printf("== 树的详细信息: \n");
        RB_Print_Tree(root);
        printf("\n");
        fflush(stdout);
    }

    printf("== 前序遍历: ");
    RB_Pre_Order_Tree(root);

    printf("\n== 中序遍历: ");
    RB_In_Order_Tree(root);

    printf("\n== 后序遍历: ");
    RB_Post_Order_Tree(root);
    printf("\n");

    int i = 0;
    if (RB_Minimum_Tree(root, &i) == 0)
        printf("== 最小值: %d\n", i);
    if (RB_Maximum_Tree(root, &i) == 0)
        printf("== 最大值: %d\n", i);
    printf("== 树的详细信息: \n");
    RB_Print_Tree(root);
    printf("\n");

    for (i = 0; i < len; i++) {
        RB_Delete_Tree(root, a[i]);

        printf("== 删除节点: %d\n", a[i]);
        if (root) {
            printf("== 树的详细信息: \n");
            RB_Print_Tree(root);
            printf("\n");
        }
    }

    RB_Destroy_Tree(root);
}
















